#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;

typedef struct BiTnode{
    BiTnode *lchild,*rchild;
    int data;
}BiTnode,*BiTree;
BiTree newNode(int data){
    BiTree node=(BiTree)malloc(sizeof(struct BiTnode));
    node->data=data;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}
BiTree createBinarySearchTree(BiTree node,int data){
    if(!node)
        return newNode(data);
    if(node->data>data){
        node->lchild=createBinarySearchTree(node->lchild,data);
    }else{
        node->rchild=createBinarySearchTree(node->rchild,data);
    }
    return node;//返回 插入了节点的 根节点
}
void preOrder_Iterative(BiTree root){
    if(NULL==root)
        return ;
    stack<BiTree> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        BiTree node=nodeStack.top();
        printf("%d ",node->data);
        nodeStack.pop();
        if(node->rchild) nodeStack.push(node->rchild);
        if(node->lchild) nodeStack.push(node->lchild);
    }
}
void postOrder_Iterative(BiTree root){
    if(NULL==root)
        return ;
    stack<BiTree> nodeStack;
    stack<BiTree> resStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        BiTree node=nodeStack.top();
        resStack.push(node);
        nodeStack.pop();
        if(node->lchild) nodeStack.push(node->lchild);
        if(node->rchild) nodeStack.push(node->rchild);
    }
    while(!resStack.empty()){
        printf("%d ",resStack.top()->data);
        resStack.pop();
    }
}
void inOrder_Iterative(BiTree root){
    if(NULL==root)
        return ;
    stack<BiTree> nodeStack;
    BiTree curNode;
    curNode=root;
    while(curNode||!nodeStack.empty()){
        while(curNode){
            nodeStack.push(curNode);
            curNode=curNode->lchild;
        }
        curNode=nodeStack.top();
        printf("%d ",curNode->data);
        nodeStack.pop();
        curNode=curNode->rchild;
    }
}
BiTree minValNode(BiTree root){
    if(NULL==root)
        return root;
    BiTree curNode=root;
    while(curNode->lchild){
        //往左找
        curNode=curNode->lchild;
    }
    return curNode;
}
/*
*删除某个节点：
*1.叶子节点直接删
*2.要删除的节点只有一个子节点 子节点替，然后删除子节点
*3.要删除的节点有两个子节点 往左找最大或者往右找最小的(中序遍历中待删除节点x的后继y)，按2的方法操作
*@返回值 BiTree 是deleteNode后新树的根节点
*@param root 是每次递归时的节点（初始为原bst树的根节点）
*@param key 是待删除节点的值
*/
BiTree deleteNode(BiTree root,int key){
    if(NULL==root)
        return root;
    if(key<root->data)
        root->lchild=deleteNode(root->lchild,key);
    else if(key>root->data)
        root->rchild=deleteNode(root->rchild,key);
    else{
        if(root->lchild==NULL){//只有一个叶子节点或者无节点
            BiTree temp=root->rchild;
            free(root);
            return temp;//这里因为递归 首先出去的 是root的右子树，所以取右孩子先考虑
        }
        if(root->rchild==NULL){
            BiTree temp=root->lchild;
            free(root);
            return temp;
        }
        //两个子节点：找右子树最小元素
        BiTree temp=minValNode(root->rchild);
        root->data=temp->data;
        root->rchild=deleteNode(root->rchild,temp->data);
    }
    return root;
}
int main(){
    BiTree root=NULL;
    int array[6] = { 10,20,30,40,50,25};
	for (int i = 0;i < 6;i++)
	{
		root=createBinarySearchTree(root, array[i]);
	}
    /*
     * 树的结构如下:
    10
       \
        20
          \
           30
          /  \
        25    40
    */ 
    printf("\n-------前序非递归-------\n");
    preOrder_Iterative(root);
    printf("\n-------中序非递归-------\n");
    inOrder_Iterative(root);
    printf("\n-------后序非递归-------\n");
    postOrder_Iterative(root);
    root=deleteNode(root,20);
    printf("\n-------后序非递归-------\n");
    postOrder_Iterative(root);
    return 0;
}